package com.leetcode.algorithm.y22.m07.w4;

import com.leetcode.algorithm.common.ListNode;

/**
 * 25. K 个一组翻转链表
 * 
 * https://leetcode.cn/problems/reverse-nodes-in-k-group/
 * 
 * @author jie.deng
 *
 */
class Question0025Solution01 {
	
	public ListNode reverseKGroup(ListNode head, int k) {
		ListNode sentinel = new ListNode();
		sentinel.next = head;

		ListNode prev = sentinel;
		ListNode next = null;

		while (prev != null && prev.next != null) {
			ListNode first = prev.next;
			ListNode last = null;
			ListNode cur = first;
			int cnt = k;
			while (cnt > 1 && cur != null) {
				cur = cur.next;
				cnt--;
			}
			if (cnt == 1 && cur != null) {
				last = cur;
				next = cur.next;
				
				// 断开与[first...last]K个节点与之前链表的连接
				prev.next = null;
				last.next = null;
				
				// 翻转[first...last]K个节点
				reverse(first);
				prev.next = last;
				first.next = next;

				// 更新prev
				prev = first;
			} else {
				break;
			}
		}

		return sentinel.next;
	}

	private void reverse(ListNode head) {
		if (head == null || head.next == null) {
			return;
		}
		reverse(head.next);
		head.next.next = head;
		head.next = null;
	}
	
}